package sortTests;

import java.util.List;
import java.util.Random;

public class QuickSort implements ISorter {

	@Override
	public void sort(List<Integer> array) {
		if (array.size() <= 1) return;
		Random random = new Random();
		int pivotIndex = random.nextInt(array.size()-1);
		int pivot = array.get(pivotIndex);
		int i = 0;
		int j = array.size() - 1;
		do {
			while (array.get(i) < pivot) i++;
			while (array.get(j) > pivot) j--;
			if (array.get(i) >= array.get(j)) {
				if (i <= j) {
					int t = array.get(i);
					array.set(i, array.get(j));
					array.set(j, t);
					i++;
					j--;
				}
			}
		} while (i <= j);
		sort(array.subList(0, i));
		sort(array.subList(i, array.size()));
	}

}
